package com.company;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LengthAll {
    /**
     * 回文子序列最长长度（不连续）
     * @param s
     * @return
     */
    public static int longestPalindromeSubseq(String s) {
        int length = s.length();
        int[][] dp = new int[length][length];
        List<String> childs = new ArrayList<>();
        //这里i要从最后一个开始遍历
        for (int i = length - 1; i >= 0; i--) {
            //单个字符也是一个回文串
            dp[i][i] = 1;
            //j从i的下一个开始
            for (int j = i + 1; j < length; j++) {
                //下面是递推公式
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        System.out.println(childs);
        return dp[0][length - 1];
    }

    /**
     * 回文子串(连续)数量
     * 所有回文子串
     * @param s
     * @return
     */
    public static int countSubstrings(String s) {
        int length = s.length();
        boolean[][] dp = new boolean[length][length];
        int count = 0;//回文串的数量
        //字符串从后往前判断
        List<String> childs = new ArrayList<>();
        for (int i = length - 1; i >= 0; i--) {
            for (int j = i; j < length; j++) {
                //如果i和j指向的字符不一样，那么dp[i][j]就
                //不能构成回文字符串
                if (s.charAt(i) != s.charAt(j))
                    continue;
                dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
                //如果从i到j能构成回文串，count就加1
                if (dp[i][j]) {
                    count++;
                    childs.add(s.substring(i, j+1));
                }
            }
        }
        System.out.println(childs);
        return count;
    }

    /**
     * 最长上升子序列长度
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        //边界条件判断
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        //初始化数组dp的每个值为1
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                //如果当前值nums[i]大于nums[j]，说明nums[i]可以和
                //nums[j]结尾的上升序列构成一个新的上升子序列
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    //记录构成的最大值
                    max = Math.max(max, dp[i]);
                }
            }
        }
        return max;
    }

    /**
     * 最长公共子串长度
     * @param str1
     * @param str2
     * @return
     */
    public static int maxLong1(String str1, String str2) {
        if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0)
            return 0;
        int max = 0;
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = 0;
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }

    /**
     * 最长公共子序列长度
     * @param str1
     * @param str2
     * @return
     */
    public static int maxLong2(String str1, String str2) {
        if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0)
            return 0;
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[str1.length()][str2.length()];
    }

    /**
     * 最大和的连续子数组的和
     * @param num
     * @return
     */
    public int maxSubArray(int[] num) {
        int length = num.length;
        int[] dp = new int[length];
        //边界条件
        dp[0] = num[0];
        int max = dp[0];
        for (int i = 1; i < length; i++) {
            //转移公式
            dp[i] = Math.max(dp[i - 1], 0) + num[i];
            //记录最大值
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    /**
     * 二位数组（三角形）最小路径和
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        //定义一个二维数组
        int[][] dp = new int[triangle.size() + 1][triangle.size() + 1];
        //从最后一行开始计算
        for (int i = triangle.size() - 1; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                //递归公式
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }

    /**
     * 二位数组（矩阵）最小路径和
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0)
                    continue;
                if (i == 0) {
                    //第一行只能从左边走过来
                    grid[i][j] += grid[i][j - 1];
                } else if (j == 0) {
                    //第一列只能从上面走下来
                    grid[i][j] += grid[i - 1][j];
                } else {
                    //递推公式，取从上面走下来和从左边走过来的最小值+当前坐标的值
                    grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
                }
            }
        }
        return grid[m - 1][n - 1];
    }
}
